package com.算法.递归_查找_排序;

import java.util.Arrays;

public class QuickSort {
    /*
     * 快速排序
     *  快速排序流程：
     *      (1) 从数列中挑出一个基准值。
     *      (2) 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；
     *          在这个分区退出之后，该基准就处于数列的中间位置。
     *      (3) 递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序。
     *
     * 参数说明：
     *     a -- 待排序的数组
     *     l -- 数组的左边界(例如，从起始位置开始排序，则l=0)
     *     r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
     */
    public static void main(String[] args) {
        int[] arr = {5,6,4,3,8,7,9,2,1};
        long befor = System.currentTimeMillis();

        quick_sort(arr,0,arr.length-1);

        System.out.println(Arrays.toString(arr));
        long after = System.currentTimeMillis();

        System.out.println(befor-after+"ms");

    }

    static void quick_sort(int a[], int l, int r)
    {
        if (l < r)
        {
            int i,j,x;

            i = l;
            j = r;
            x = a[i];
            while (i < j)
            {
                while(i < j && a[j] > x) {
                    j--; // 从右向左找第一个小于x的数
                }
                if(i < j) {
                    a[i++] = a[j];
                }
                while(i < j && a[i] < x) {
                    i++; // 从左向右找第一个大于x的数
                }
                if(i < j) {
                    a[j--] = a[i];
                }
            }
            a[i] = x;
            quick_sort(a, l, i-1); /* 递归调用 */
            quick_sort(a, i+1, r); /* 递归调用 */
        }
    }
}
